<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<META http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" href="../../../style.css" type="text/css" media="screen">
<link rel="stylesheet" href="../../../print.css" type="text/css" media="print">
<meta content="GameTrees,com.godpaper.util.GameTrees,winner,alpha,beta,depth,AlphaBeta,DR,ETC,MTDF,MaxMove,MinMax,MinMove,NegaMax,PVS,QS,SE,Windowing,doEvaluation" name="keywords">
<title>com.godpaper.util.GameTrees</title>
</head>
<body>
<script type="text/javascript" language="javascript" src="../../../asdoc.js"></script><script type="text/javascript" language="javascript" src="../../../cookies.js"></script><script type="text/javascript" language="javascript">
<!--
				asdocTitle = 'GameTrees - Old Nine Chess';
				var baseRef = '../../../';
				window.onload = configPage;
			--></script>
<table style="display:none" id="titleTable" cellspacing="0" cellpadding="0" class="titleTable">
<tr>
<td align="left" class="titleTableTitle">OldNineChess</td><td align="right" class="titleTableTopNav"><a onclick="loadClassListFrame('../../../all-classes.html')" href="../../../package-summary.html">All&nbsp;Packages</a>&nbsp;|&nbsp;<a onclick="loadClassListFrame('../../../all-classes.html')" href="../../../class-summary.html">All&nbsp;Classes</a>&nbsp;|&nbsp;<a onclick="loadClassListFrame('../../../index-list.html')" href="../../../all-index-A.html">Index</a>&nbsp;|&nbsp;<a href="../../../index.html?com/godpaper/util/GameTrees.html&amp;com/godpaper/util/class-list.html" id="framesLink1">Frames</a><a onclick="parent.location=document.location" href="" style="display:none" id="noFramesLink1">No&nbsp;Frames</a></td><td rowspan="3" align="right" class="titleTableLogo"><img alt="Adobe Logo" title="Adobe Logo" class="logoImage" src="../../../images/logo.jpg"></td>
</tr>
<tr class="titleTableRow2">
<td align="left" id="subTitle" class="titleTableSubTitle">Class&nbsp;GameTrees</td><td align="right" id="subNav" class="titleTableSubNav"><a href="#propertySummary">Properties</a>&nbsp;| <a href="#methodSummary">Methods</a></td>
</tr>
<tr class="titleTableRow3">
<td colspan="2">&nbsp;</td>
</tr>
</table>
<script type="text/javascript" language="javascript">
<!--
if (!isEclipse() || window.name != ECLIPSE_FRAME_NAME) {titleBar_setSubTitle("Class GameTrees"); titleBar_setSubNav(false,true,false,false,false,false,true,false,false,false,false,false,false,false);}
--></script>
<div class="MainContent">
<table cellspacing="0" cellpadding="0" class="classHeaderTable">
<tr>
<td class="classHeaderTableLabel">Package</td><td><a onclick="javascript:loadClassListFrame('class-list.html')" href="package-detail.html">com.godpaper.util</a></td>
</tr>
<tr>
<td class="classHeaderTableLabel">Class</td><td class="classSignature">public class GameTrees</td>
</tr>
</table>
<p></p>
    This essay is a detailed explanation of one of the most important
   data structures ever created for Game Artificial Intelligence. 
  The minimax tree is at the heart of almost every board game program in existence.
  <p></p>
<br>
<hr>
</div>
<a name="propertySummary"></a>
<div class="summarySection">
<div class="summaryTableTitle">Public Properties</div>
<table id="summaryTableProperty" class="summaryTable " cellpadding="3" cellspacing="0">
<tr>
<th>&nbsp;</th><th colspan="2">Property</th><th class="summaryTableOwnerCol">Defined&nbsp;by</th>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#alpha">alpha</a> : int<div class="summaryTableDescription">
   </div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#beta">beta</a> : int<div class="summaryTableDescription">
   
   </div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#depth">depth</a> : int<div class="summaryTableDescription">
   
   </div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
</table>
</div>
<a name="protectedPropertySummary"></a>
<div class="summarySection">
<div class="summaryTableTitle">Protected Properties</div>
<table id="summaryTableProtectedProperty" class="summaryTable " cellpadding="3" cellspacing="0">
<tr>
<th>&nbsp;</th><th colspan="2">Property</th><th class="summaryTableOwnerCol">Defined&nbsp;by</th>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#winner">winner</a> : <a href="../game/chess/twoHitOne/Winner.html">Winner</a>
<div class="summaryTableDescription"></div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
</table>
</div>
<a name="methodSummary"></a>
<div class="summarySection">
<div class="summaryTableTitle">Public Methods</div>
<table id="summaryTableMethod" class="summaryTable " cellpadding="3" cellspacing="0">
<tr>
<th>&nbsp;</th><th colspan="2">Method</th><th class="summaryTableOwnerCol">Defined&nbsp;by</th>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#GameTrees()">GameTrees</a>()</div>
<div class="summaryTableDescription"></div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#AlphaBeta()">AlphaBeta</a>(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, depth:int, alpha:int, beta:int):void</div>
<div class="summaryTableDescription">
   
   The major improvement over MiniMax/NegaMax is the AlphaBeta algorithm: 
   Here you realize that you don't have to go through the whole search tree.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#doEvaluation()">doEvaluation</a>(postion:<a href="TwoDimensionArray.html">TwoDimensionArray</a>):Number</div>
<div class="summaryTableDescription"></div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#DR()">DR</a>():void</div>
<div class="summaryTableDescription">
   epth reductions 
   Pruning in general is a way of deciding to reduce the search depth of the current line.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#ETC()">ETC</a>():void</div>
<div class="summaryTableDescription">
   Enhanced transposition cutoffs
   ETC is a cute idea: in a normal AlphaBeta search with a hashtable, 
   you will be searching through all possible moves, and for every move you make, 
   you do a hashtable lookup to see if you can return immediately.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#MaxMove()">MaxMove</a>():void</div>
<div class="summaryTableDescription"></div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#MinMax()">MinMax</a>(player:<a href="../game/chess/twoHitOne/Player.html">Player</a>, board:<a href="../game/chess/twoHitOne/Board.html">Board</a>):<a href="../game/chess/twoHitOne/Winner.html">Winner</a>
</div>
<div class="summaryTableDescription">
      if(game over in current board position)
         return winner
         children = all legal moves for player from this board
         if(max's turn)
         return maximal score of calling minimax on all the children
         else (min's turn)
         return minimal score of calling minimax on all the children
         
         </div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#MinMove()">MinMove</a>():void</div>
<div class="summaryTableDescription"></div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#MTDF()">MTDF</a>(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, firstGuess:int, depth:int):void</div>
<div class="summaryTableDescription">
   MTD(f) is another clever trick which uses AlphaBeta's property of returning boundaries on the true MiniMax value.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#NegaMax()">NegaMax</a>(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, depth:int):void</div>
<div class="summaryTableDescription">
   Search enhancements
   All techniques above aimed at reducing the number of nodes to search by better move ordering.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#PVS()">PVS</a>():void</div>
<div class="summaryTableDescription">
   Principal variation searching 
   Windowing is simple and it is quite good.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#QS()">QS</a>():void</div>
<div class="summaryTableDescription">
   uiescence search 
   As I just said above, the basic search algorithm I presented always goes to a fixed depth.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#SE()">SE</a>():void</div>
<div class="summaryTableDescription">
   ingular extensions 
   Singular extensions (SE) got their 15 minutes of fame when they were used by the Deep Blue team which won it's chess match against world champion Garry Kasparov.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#Windowing()">Windowing</a>():void</div>
<div class="summaryTableDescription">
   Windowing is the simplest of the following techniques.</div>
</td><td class="summaryTableOwnerCol">GameTrees</td>
</tr>
</table>
</div>
<script type="text/javascript" language="javascript">
<!--
showHideInherited();
--></script>
<div class="MainContent">
<a name="propertyDetail"></a>
<div class="detailSectionHeader">Property detail</div>
<a name="alpha"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">alpha</td><td class="detailHeaderType">property</td>
</tr>
</table>
<div class="detailBody">
<code>alpha:int</code>&nbsp;&nbsp;[read-write]<p>
   </p><p>The default value is <code>1</code>.</p>
<span class="label">Implementation</span>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function get alpha():int</code>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function set alpha(value:int):void</code>
<br>
</div>
<a name="beta"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">beta</td><td class="detailHeaderType">property</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>beta:int</code>&nbsp;&nbsp;[read-write]<p>
   
   </p><p>The default value is <code>-1</code>.</p>
<span class="label">Implementation</span>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function get beta():int</code>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function set beta(value:int):void</code>
<br>
</div>
<a name="depth"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">depth</td><td class="detailHeaderType">property</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>depth:int</code>&nbsp;&nbsp;[read-write]<p>
   
   </p><span class="label">Implementation</span>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function get depth():int</code>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function set depth(value:int):void</code>
<br>
</div>
<a name="winner"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">winner</td><td class="detailHeaderType">property</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>protected var winner:<a href="../game/chess/twoHitOne/Winner.html">Winner</a></code>
</div>
<a name="constructorDetail"></a>
<div class="detailSectionHeader">Constructor detail</div>
<a name="GameTrees()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">GameTrees</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">constructor</td>
</tr>
</table>
<div class="detailBody">
<code>public function GameTrees()</code>
</div>
<a name="methodDetail"></a>
<div class="detailSectionHeader">Method detail</div>
<a name="AlphaBeta()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">AlphaBeta</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td>
</tr>
</table>
<div class="detailBody">
<code>public function AlphaBeta(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, depth:int, alpha:int, beta:int):void</code><p>
   
   The major improvement over MiniMax/NegaMax is the AlphaBeta algorithm: 
   Here you realize that you don't have to go through the whole search tree. 
   If you find one winning continuation, you don't have to look at any others. 
   Similarly, if you have found one continuation which will give you 
   the value V you can stop your search along another continuation 
   if you find only one possibility for your opponent 
   which gives you a lower score than V. 
   You don't have to look at all the other possibilities your opponent
    might have - one refutation is enough! 
   Here is the code for AlphaBeta, extending the earlier NegaMax code: 
   It receives two extra parameters, alpha and beta. 
   They define an interval within which the evaluation has to be. 
   If it isn't, the function will return. 
   Your first call to AlphaBeta will be with an interval -INFINITY...INFINITY; 
   subsequent recursive calls to the function will make the window smaller. 
   
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">position</span>:<a href="TwoDimensionArray.html">TwoDimensionArray</a></code> &mdash; the piece's postion in board.
   </td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">depth</span>:int</code> &mdash; the piece's depth in this game tree.
   </td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">alpha</span>:int</code> &mdash; INFINITY.
   </td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">beta</span>:int</code> &mdash; -INFINITY.
   
   </td>
</tr>
</table>
</div>
<a name="doEvaluation()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">doEvaluation</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function doEvaluation(postion:<a href="TwoDimensionArray.html">TwoDimensionArray</a>):Number</code><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">postion</span>:<a href="TwoDimensionArray.html">TwoDimensionArray</a></code></td>
</tr>
</table>
<p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>Number</code></td>
</tr>
</table>
</div>
<a name="DR()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">DR</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function DR():void</code><p>
   epth reductions 
   Pruning in general is a way of deciding to reduce the search depth of the current line. 
   There are many ways in which you can do this, and some of them are game specific (see below). 
   Others are of a more general nature. The whole idea comes from the fact that most of the lines your program is looking at are absolutely ridiculous. 
   Now, if we could only get rid of these ridiculous lines and look at the important ones instead... 
   One very general pruning technique that is nearly guaranteed to work in most games is Michael Buro's ProbCut algorithm (and variants thereof): 
   In ProbCut, you decide to search less deeply at some fixed remaining depth, 
   e.g. when there are 8 ply remaining. Instead, you decide to search only 4 ply. 
   Now, if this search returns a value far outside of your alpha-beta window you decide to believe the shallow search and return the result. 
   If it's not too far outside of the alpha-beta window, or even inside it, you have to re-search to the full depth. 
   There are a lot of constants you can tune in this algorithm, and you will have to experiment with it to get it up to full strength. 
   It was used by Buro himself in his world-class Othello program Logistello, and I once implemented a version of Multi-ProbCut in my checkers program Cake. 
   It worked much better than plain alphabeta, but not as well as my game-specific pruning algorithm. 
   Nevertheless, ProbCut is highly interesting since it doesn't depend on the game you are playing. 
   To me it's no surprise that it is outperformed by reduction algorithms which know something about the game - after all, 
   these have some knowledge advantage! 
   </p></div>
<a name="ETC()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">ETC</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function ETC():void</code><p>
   Enhanced transposition cutoffs
   ETC is a cute idea: in a normal AlphaBeta search with a hashtable, 
   you will be searching through all possible moves, and for every move you make, 
   you do a hashtable lookup to see if you can return immediately. 
   ETC takes this idea one step further: Before doing your recursive AlphaBeta call, 
   you look up all possible successor positions of the current position. 
   If you get a hashtable hit on one of these calls which gives you a return value > beta, 
   you can immediately return without a search. 
   The reason ETC helps is that in the normal AlphaBeta case, 
   you generate a movelist, and let's assume that move number 5 would lead to a hashtable hit leading to a cutoff. 
   Nevertheless, in the normal AlphaBeta framework, 
   you will have to search through moves number 1 - 4, 
   and only then do you find that move number 5 gives you a cutoff. 
   This search is made unnecessary with the ETC lookup. 
   
   </p></div>
<a name="MaxMove()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">MaxMove</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function MaxMove():void</code>
</div>
<a name="MinMax()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">MinMax</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function MinMax(player:<a href="../game/chess/twoHitOne/Player.html">Player</a>, board:<a href="../game/chess/twoHitOne/Board.html">Board</a>):<a href="../game/chess/twoHitOne/Winner.html">Winner</a></code><p>
      if(game over in current board position)
         return winner
         children = all legal moves for player from this board
         if(max's turn)
         return maximal score of calling minimax on all the children
         else (min's turn)
         return minimal score of calling minimax on all the children
         
         </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">player</span>:<a href="../game/chess/twoHitOne/Player.html">Player</a></code> &mdash; the chess game player.
   </td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">board</span>:<a href="../game/chess/twoHitOne/Board.html">Board</a></code> &mdash; the chess game board.
   </td>
</tr>
</table>
<p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code><a href="../game/chess/twoHitOne/Winner.html">Winner</a></code> &mdash; 
                        the winner of this game.
   
   
                        
                     </td>
</tr>
</table>
</div>
<a name="MinMove()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">MinMove</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function MinMove():void</code>
</div>
<a name="MTDF()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">MTDF</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function MTDF(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, firstGuess:int, depth:int):void</code><p>
   MTD(f) is another clever trick which uses AlphaBeta's property of returning boundaries on the true MiniMax value.
   MTD(f) makes a few calls to AlphaBeta with changing windows to get the true value of the position. 
   Each time it gets either a lower or an upper bound on the current position's value. 
   These bounds converge toward the true MiniMax value.
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">position</span>:<a href="TwoDimensionArray.html">TwoDimensionArray</a></code></td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">firstGuess</span>:int</code></td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">depth</span>:int</code></td>
</tr>
</table>
</div>
<a name="NegaMax()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">NegaMax</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function NegaMax(position:<a href="TwoDimensionArray.html">TwoDimensionArray</a>, depth:int):void</code><p>
   Search enhancements
   All techniques above aimed at reducing the number of nodes to search by better move ordering. 
   There is another class of enhancements with the same goal, but with different means. 
   These enhancements try to exploit the nature of the AlphaBeta algorithm, 
   which has to search fewer nodes when the alpha-beta window is smaller. 
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">position</span>:<a href="TwoDimensionArray.html">TwoDimensionArray</a></code></td>
</tr>
<tr>
<td class="paramSpacer">&nbsp;</td>
</tr>
<tr>
<td width="20px"></td><td><code><span class="label">depth</span>:int</code></td>
</tr>
</table>
</div>
<a name="PVS()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">PVS</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function PVS():void</code><p>
   Principal variation searching 
   Windowing is simple and it is quite good. 
   However, windowing is restricted to the root node. 
   PVS tries to go a bit further by making assumptions on the alpha-beta window at every node. Here's the basic idea: Since we have gone to a lot of trouble with our move ordering schemes above, we can be pretty confident that we will find the best move early on. Therefore, our localalpha will be at its maximal value after the first few moves. PVS tries to exploit this by calling the next recursion of AlphaBeta with different parameters than standard-AlphaBeta. AlphaBeta would use alpha and beta. In PVS however, we already guess that our current localalpha will be better than what we will get with the remaining moves. Therefore we set alpha to localalpha and beta to localalpha+1, that is, we use a call 
   value=-alphabeta(p,d-1,-(localalpha+1),-localalpha);
   We expect this call to fail low, because we believe that we have already 
   found the best move. If this call does not fail low, 
   we need to revise our assumption and call AlphaBeta again 
   with the normal alpha and beta bounds.
   PVS is also often called NegaScout. 
   It gets its name from the scout search which a minimal window,
   which sort of probes the territory to see whether a real search is necessary. 
   </p></div>
<a name="QS()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">QS</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function QS():void</code><p>
   uiescence search 
   As I just said above, the basic search algorithm I presented always goes to a fixed depth. 
   However, it may often not be a good idea to evaluate a position if it is too chaotic. 
   Exactly what too chaotic might mean depends on the game. 
   A simple example in chess is a position where white to move is a rook down but can promote a pawn to a queen, 
   winning the game. If we were to call our static evaluation function in this position, 
   it would (unless it was smart, which evaluation functions usually aren't) conclude that white is dead lost, 
   a rook down. Therefore, a technique called quiescence search is often used: Once you want to call your evaluation function, 
   you take a look at very few select moves that need to be checked further. You have to make sure that you are very restrictive in your quiescence search, 
   otherwise your search tree will explode completely. 
   </p></div>
<a name="SE()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">SE</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function SE():void</code><p>
   ingular extensions 
   Singular extensions (SE) got their 15 minutes of fame when they were used by the Deep Blue team which won it's chess match against world champion Garry Kasparov.
   Since then, SE seems to have been abandoned by most. The idea of singular extensions is appealing, 
   and what makes it so appealing is that it is game-independent: Many ideas on how to improve tree search depend heavily on the game, and therefore lack generality. Singular extensions in theory work for all games. 
   As the name says, SE is about extensions. Up to now, I have avoided this topic, 
   but it is important: The AlphaBeta function I have shown searches a game tree to a fixed depth. 
   However, many lines of play are just stupid, while others are more interesting. 
   The aim of SE is to catch some of the more interesting lines, 
   and to search them deeper than the rest. It relies on detecting forced moves for one side, and on extending the search depth in the case of forced moves. Humans play chess like this, and can solve long variations which are forced easily. SE tries to emulate this behavior.
   </p></div>
<a name="Windowing()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">Windowing</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function Windowing():void</code><p>
   Windowing is the simplest of the following techniques.
   In an iterative deepening framework, we always have a value of the previous iteration.
   Therefore, we try to reduce the search effort by using a smaller alpha-beta window. 
   Instead of using -INFINITY...+INFINITY we can use an interval lastvalue-WINDOW...lastvalue+WINDOW. 
   If the true MiniMax value at this iteration is really inside this window, 
   we will just need to search fewer nodes than with the larger window. 
   On the other hand, 
   our guess that the true value is inside this window might also be wrong. 
   In this case, we will get a fail-high or a fail-low. In this case, 
   we will have to do a re-search with a larger window. 
   </p></div>
<br>
<br>
<hr>
<br>
<p></p>
<center class="copyright"> 
</center>
</div>
</body>
</html>
<!-- -->
